// 统计所有小于非负整数 n 的质数的数量。

const countPrimes = function (n: number) {
    const isPrime: boolean[] = new Array(n).fill(true);// 埃式筛基本表格
    for (let i = 2; i < n; i++) {// 从质数二开始遍历
        if (isPrime[i]) {
            // 找到一个质数，填满它的所有对应表格
            for (let j = i * 2; j < isPrime.length; j += i) {
                isPrime[j] = false;
            }
        }
    }
    let count: number = 0;// 计数变量
    // 开始计数
    for (let i = 2; i < n; i++) {
        if (isPrime[i] === true) count++;
    }
    return count;
};



countPrimes(10);


// 这道题目其实知道方法的难度下并不大
// 首先最好想到的就是常规的枚举破解算法，这里只需要注意一个点：
// 破解算法中，判断一个数n是否是素数时，枚举因数只需要截止到根号n即可
// 然后引出本题的巧妙解法：埃式筛算法
// 埃式筛先初始化一个n大小长度的表格，每个索引表示该数是否为质数
// 初始化情况下，我们假定每个数都是质数
// 我们扫描比n小的每个数，如果发现当前数的埃式筛索引为素数
// 那么我们重新填埃式筛，把所有该素数的倍数都填成合数（数学原理，如2是质数；2、4、6、8..就都是合数了）
// 这样的操作直到比n小的每个数都走一遍，之后从2开始扫描埃式筛
// 计数埃式筛即可得到结果。